//给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 
//
// 示例 1: 
//
// 输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
// 
//
// 示例 2: 
//
// 输入: nums = [1], k = 1
//输出: [1] 
//
// 说明： 
//
// 
// 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 
// 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 
// 
// Related Topics 堆 哈希表


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun topKFrequent(nums: IntArray, k: Int): List<Int> {
        val map = java.util.HashMap<Int, Int>()
        for (num in nums) {
            map[num] = (map[num]?.plus(1)) ?: 1
        }
        val heap = java.util.PriorityQueue<Int>(k, java.util.Comparator<Int> { o1, o2 ->
            (map[o1] ?: 0) - (map[o2] ?: 0)
        })
        for (item in map) {
            heap.add(item.key)
            if (heap.size > k) {
                heap.poll()
            }
        }
        val result = ArrayList<Int>()
        while (!heap.isEmpty()) {
            result.add(heap.poll())
        }

        return result//.reversed()
    }
}
//leetcode submit region end(Prohibit modification and deletion)
